package com.kevin.Code.Array;

import java.util.Arrays;

/**
 * @author Vinlee Xiao
 * @Classname KthLargestElementinanArray
 * @Description Leetcode 215. 数组中的第K个最大元素 中等难度 高频题 思路很简单
 * @Date 2021/11/2 20:44
 * @Version 1.0
 */
public class KthLargestElementinanArray {

    /**
     * 手写快速排序
     *
     * @param nums
     * @param k
     * @return
     */
    public int findKthLargest(int[] nums, int k) {
        int len = nums.length;

        quickSortByNum(nums, 0, len - 1);

        return nums[len - k];
    }

    /**
     * @param nums
     * @param k
     * @return
     */
    public int findKthLargest1(int[] nums, int k) {

        int len = nums.length;

        return 0;
    }

    /**
     * 手写快速排序
     *
     * @param nums
     */
    private static void quickSortByNum(int[] nums, int low, int high) {

        if (low >= high) {
            return;
        }

        int tmp = nums[low];

        int i = low;
        int j = high;

        while (i < j) {

            while (i < j && nums[j] >= tmp) {
                j--;
            }

            while (i < j && nums[i] <= tmp) {
                i++;
            }

            if (i < j) {
                int temp = nums[j];
                nums[j] = nums[i];
                nums[i] = temp;
            }
        }
        nums[low] = nums[j];
        nums[j] = tmp;


        quickSortByNum(nums, low, j - 1);
        quickSortByNum(nums, j + 1, high);
    }

    public static void main(String[] args) {
        int[] nums = new int[]{-1, 2, 0};
        quickSortByNum(nums, 0, nums.length - 1);
        for (int num : nums) {
            System.out.println(num);
        }
    }
}
